package agorithm.week1.classTwo;

/**
 * 53. 最大子序和
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 示例 2：
 *
 * 输入：nums = [1]
 * 输出：1
 * 示例 3：
 *
 * 输入：nums = [0]
 * 输出：0
 * 示例 4：
 *
 * 输入：nums = [-1]
 * 输出：-1
 * 示例 5：
 *
 * 输入：nums = [-100000]
 * 输出：-100000
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 3 * 104
 * -105 <= nums[i] <= 105
 *
 * @author zcc
 * @date 2021/05/26/17:26
 */
public class MaximumSumArray {
    public static void main(String[] args) {
        int[] digits = {1,1,1};
        int arr = maxSubArray1(digits);
        System.out.println("max = " + arr);
    }
    public static int maxSubArray1(int[] nums) {
        int[] sum = new int[nums.length+1];
        for ( int i = 1 ;i < sum.length ;i++){
            sum[i] = sum[i-1] + nums[i-1];
        }
        int max = - Integer.MAX_VALUE;
        for ( int i = 0 ;i < sum.length ;i++){
            for ( int j = 0 ;j < i;j++){
                int s = sum[i] - sum[j];
                max = s > max ? s : max;
            }
        }
        return max;
    }

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i]=dp[i-1]<0?nums[i]:dp[i-1]+nums[i];
            max = dp[i]>max?dp[i]:max;
        }
        return max;
    }
}
